// Created by WXX on 2022/1/4 21:16
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

/**
 * 执行用时：36 ms, 在所有 C++ 提交中击败了64.15%的用户
 * 内存消耗：9.2 MB, 在所有 C++ 提交中击败了69.81%的用户
 */
const int N = 55;

int f[N * 2][N][N];

class Solution {
public:
    int n;
    vector<vector<int>> g;

    int dp(int k, int i, int j) {
        int &v = f[k][i][j];
        if (v != -1) return v;
        if (k > n * 2) return v = 0;
        if (!i) return v = 1;
        if (i == j) return v = 2;

        if (k % 2 == 0) {
            int cnt = 0;
            for (int x : g[i]) {
                int t = dp(k + 1, x, j);
                if (t == 1) return v = 1;
                if (!t) cnt++;
            }
            if (cnt) return v = 0;
            return 2;
        } else {
            int cnt = 0;
            for (int x : g[j]) {
                if (!x) continue;
                int t = dp(k + 1, i, x);
                if (t == 2) return v = 2;
                if (!t) cnt++;
            }
            if (cnt) return v = 0;
            return 1;
        }
    }

    int catMouseGame(vector<vector<int>>& graph) {
        g = graph;
        n = g.size();
        memset(f, -1, sizeof f);
        return dp(0, 1, 2);
    }
};

int main() {

    vector<vector<int>> graph = {
            {2, 5},
            {3},
            {0, 4, 5},
            {1, 4, 5},
            {2, 3},
            {0, 2, 3}
    };
    cout << Solution().catMouseGame(graph) << endl;  // 0

    return 0;
}
